{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. Add Two Numbers** <font color=#f0ad4e size=3>_medium_</font>\n",
    "\n",
    "You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.\n",
    "\n",
    "You may assume the two numbers do not contain any leading zero, except the number 0 itself.\n",
    "\n",
    "**Example**\n",
    "```\n",
    "Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)  \n",
    "Output: 7 -> 0 -> 8  \n",
    "Explanation: 342 + 465 = 807.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "0\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "def addTwoNumbers(l1, l2):\n",
    "    \"\"\"\n",
    "    Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)\n",
    "    Output: 7 -> 0 -> 8\n",
    "    Explanation: 342 + 465 = 807.\n",
    "    \"\"\"\n",
    "    head1, head2 = l1, l2\n",
    "\n",
    "    sum = head1.val + head2.val\n",
    "    carry = sum // 10\n",
    "    head3 = l3 = ListNode(sum % 10)\n",
    "\n",
    "    head1 = head1.next\n",
    "    head2 = head2.next\n",
    "    while head1 is not None:\n",
    "        sum = (head1.val + head2.val + carry) % 10\n",
    "        carry = (head1.val + head2.val + carry) // 10\n",
    "        head3.next = ListNode(sum)\n",
    "\n",
    "        head1 = head1.next\n",
    "        head2 = head2.next\n",
    "        head3 = head3.next\n",
    "\n",
    "    if carry > 0:\n",
    "        head3.next = ListNode(carry)\n",
    "\n",
    "    return l3\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    l1 = ListNode(2)\n",
    "    l1.next = ListNode(4)\n",
    "    l1.next.next = ListNode(3)\n",
    "\n",
    "    l2 = ListNode(5)\n",
    "    l2.next = ListNode(6)\n",
    "    l2.next.next = ListNode(8)\n",
    "\n",
    "    ret = addTwoNumbers(l1, l2)\n",
    "\n",
    "    while ret is not None:\n",
    "        print(ret.val)\n",
    "        ret = ret.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
